{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Number of Ways to Build House of Cards"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #math #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数学 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: houseOfCards"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #建造纸牌屋的方法数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数 <code>n</code>，代表你拥有牌的数量。一个&nbsp;<strong>纸牌屋&nbsp;</strong>满足以下条件:</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>一个<strong> 纸牌屋&nbsp;</strong>由一行或多行&nbsp;<strong>三角形</strong> 和水平纸牌组成。</li>\n",
    "\t<li><strong>三角形&nbsp;</strong>是由两张卡片相互靠在一起形成的。</li>\n",
    "\t<li>一张卡片必须水平放置在一行中&nbsp;<strong>所有相邻&nbsp;</strong>的三角形之间。</li>\n",
    "\t<li>比第一行高的任何三角形都必须放在前一行的水平牌上。</li>\n",
    "\t<li>每个三角形都被放置在行中&nbsp;<strong>最左边&nbsp;</strong>的可用位置。</li>\n",
    "</ul>\n",
    "\n",
    "<p>返回<em>使用所有 <code>n</code> 张卡片可以构建的不同纸牌屋的数量</em>。如果存在一行两个纸牌屋包含不同数量的纸牌，那么两个纸牌屋被认为是不同的。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong class=\"example\">示例 1:</strong></p>\n",
    "<img src=\"https://assets.leetcode.com/uploads/2022/02/27/image-20220227213243-1.png\" style=\"width: 726px; height: 150px;\" />\n",
    "<pre>\n",
    "<strong>输入:</strong> n = 16\n",
    "<strong>输出:</strong> 2\n",
    "<strong>解释:</strong> 有两种有效的纸牌屋摆法。\n",
    "图中的第三个纸牌屋无效，因为第一行最右边的三角形没有放在水平纸牌的顶部。\n",
    "</pre>\n",
    "\n",
    "<p><strong class=\"example\">Example 2:</strong></p>\n",
    "<img src=\"https://assets.leetcode.com/uploads/2022/02/27/image-20220227213306-2.png\" style=\"width: 96px; height: 80px;\" />\n",
    "<pre>\n",
    "<strong>输入:</strong> n = 2\n",
    "<strong>输出:</strong> 1\n",
    "<strong>解释:</strong> 这是唯一可行的纸牌屋。</pre>\n",
    "\n",
    "<p><strong class=\"example\">Example 3:</strong></p>\n",
    "<img src=\"https://assets.leetcode.com/uploads/2022/02/27/image-20220227213331-3.png\" style=\"width: 330px; height: 85px;\" />\n",
    "<pre>\n",
    "<strong>输入:</strong> n = 4\n",
    "<strong>输出:</strong> 0\n",
    "<strong>解释:</strong> 图中的三种纸牌都是无效的。\n",
    "第一个纸牌屋需要在两个三角形之间放置一张水平纸牌。\n",
    "第二个纸牌屋使用 5 张纸牌。\n",
    "第三个纸牌屋使用 2 张纸牌。</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= n &lt;= 500</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [number-of-ways-to-build-house-of-cards](https://leetcode.cn/problems/number-of-ways-to-build-house-of-cards/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [number-of-ways-to-build-house-of-cards](https://leetcode.cn/problems/number-of-ways-to-build-house-of-cards/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['16', '2', '4']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def houseOfCards(self, n: int) -> int:\n",
    "        dp = [1] + [0] * 500\n",
    "        for i in range(2, 500 + 1, 3):\n",
    "            for j in range(500, i - 1, -1):\n",
    "                dp[j] += dp[j - i]\n",
    "        return dp[n]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "pre=[]\n",
    "i=2\n",
    "while i<=500:\n",
    "    pre.append(i)\n",
    "    i+=3\n",
    "pre.sort(reverse=True)\n",
    "\n",
    "class Solution:\n",
    "    def houseOfCards(self, n: int) -> int:\n",
    "        dp=[1]+[0]*n\n",
    "        size=len(pre)\n",
    "        for i in pre:\n",
    "            for j in range(n-i+1):\n",
    "                dp[n-j]+=dp[n-j-i]\n",
    "        \n",
    "        return dp[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def houseOfCards(self, n: int) -> int:\n",
    "        @cache\n",
    "        def dfs(n,start):            \n",
    "            if n <= 1:\n",
    "                return 0\n",
    "                                                            \n",
    "            # 最低一行 \n",
    "            if (n-2) % 3 == 0:\n",
    "                res = 1\n",
    "            else:\n",
    "                res = 0\n",
    "                \n",
    "            for i in range(start,n,3):\n",
    "                rest = n - i\n",
    "                if i + 3 > rest:\n",
    "                    break\n",
    "                \n",
    "                res += dfs(rest,i+3)  \n",
    "            \n",
    "            return res\n",
    "        \n",
    "        return dfs(n,2) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def houseOfCards(self, n: int) -> int:\n",
    "\n",
    "        def cal(i):\n",
    "            return 2 + 3 * (i - 1)\n",
    "\n",
    "        @cache\n",
    "        def f(rest, pre):\n",
    "            if rest < 2:\n",
    "                return 1 - rest \n",
    "            res = 0\n",
    "            for i in range(1, 500):                \n",
    "                if cal(i) > rest or i >= pre:\n",
    "                    break \n",
    "                res += f(rest - cal(i), i)\n",
    "            return res \n",
    "        \n",
    "        return f(n, inf)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def houseOfCards(self, n: int) -> int:\n",
    "\n",
    "        def cal(i):\n",
    "            return 2 + 3 * (i - 1)\n",
    "\n",
    "        @cache\n",
    "        def f(rest, pre):\n",
    "            if rest < 2:\n",
    "                return 1 - rest \n",
    "            res = 0\n",
    "            for i in range(1, 500):                \n",
    "                if cal(i) > rest or i >= pre:\n",
    "                    break \n",
    "                res += f(rest - cal(i), i)\n",
    "            return res \n",
    "        \n",
    "        return f(n, inf)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def houseOfCards(self, n: int) -> int:\n",
    "        \"\"\"\n",
    "\n",
    "        :param n:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        oklist = set()\n",
    "        cur = 1\n",
    "        while True:\n",
    "            cur1 = 3 * cur - 1\n",
    "            if cur1 > 500 or cur1 > n:\n",
    "                break\n",
    "            oklist.add(cur1)\n",
    "            cur += 1\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def get_cnt(n1, restrict):\n",
    "            if n1 == 0:\n",
    "                return 1\n",
    "            cnt = 0\n",
    "            for i in oklist:\n",
    "                if i <= n1 and i < restrict:\n",
    "                    cnt += get_cnt(n1 - i, i)\n",
    "            return cnt\n",
    "        return get_cnt(n, n+1)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "# # dfs\n",
    "# 没太看懂题目，不过感觉状态只和 (当前行的三角形数，剩下的卡片数) 有关，所以考虑记忆化dfs搜索试一下 时间复杂度为 O(n^3)，空间复杂度为 O(n^2)\n",
    "from functools import lru_cache\n",
    "\n",
    "class Solution:\n",
    "    def houseOfCards(self, n: int) -> int:\n",
    "        @lru_cache(None)\n",
    "        def dfs(curTriangle: int, remain: int) -> int:\n",
    "            if remain <= 0:\n",
    "                return int(remain == 0)\n",
    "\n",
    "            res = 0\n",
    "            for nextTriangle in range(curTriangle):\n",
    "                res += dfs(nextTriangle, remain - 2 * nextTriangle - (nextTriangle - 1))\n",
    "\n",
    "            return res\n",
    "            \n",
    "\n",
    "        res = 0\n",
    "        for baseTriangle in range(1, n):\n",
    "            res += dfs(baseTriangle, n - 2 * baseTriangle - (baseTriangle - 1))\n",
    "\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
